import java.util.ArrayList;
import java.util.List;
//力扣78. 子集
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for(int i=0;i<=n;i++){
            List<Integer> path = new ArrayList<>();
            dfs(nums,ans,path,i,0);
        }
        return ans;
    }
    public void dfs(int[] nums,List<List<Integer>> ans,List<Integer> path,int size,int k){
        if(path.size()==size){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=k;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,ans,path,size,i+1);
            path.remove(path.size()-1);
        }
    }
}



//力扣17. 电话号码的字母组合
class Solution2 {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        int n = digits.length();
        if(n==0){
            return ans;
        }
        String[] s = new String[10];
        for(int i=2;i<=9;i++){
            if(i==2){
                s[i]="abc";
            }else if(i==3){
                s[i]="def";
            }else if(i==4){
                s[i]="ghi";
            }else if(i==5){
                s[i]="jkl";
            }else if(i==6){
                s[i]="mno";
            }else if(i==7){
                s[i]="pqrs";
            }else if(i==8){
                s[i]="tuv";
            }else if(i==9){
                s[i]="wxyz";
            }
        }
        StringBuilder path = new StringBuilder();
        dfs(digits,s,path,ans,n,0);
        return ans;
    }
    public void dfs(String digits,String[] s,StringBuilder path,List<String> ans,int n,int k){
        if(path.length()==n){
            ans.add(path.toString());
            return;
        }
        char[] c = digits.toCharArray();
        int num = c[k]-'0';
        char[] ch = s[num].toCharArray();
        for(int i=0;i<ch.length;i++){
            path.append(ch[i]);
            dfs(digits,s,path,ans,n,k+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}